package com.atcumt.CodeTop;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/* 
 * 1、二叉树的层序遍历
 * 2、二叉树的锯齿遍历
 * 3、二叉树的最近公共祖先
 * 4、股票的买卖时间
 * 5、有效的括号
 * 6、合并有序数组
 * 7、最长回文子串
 * 8、最长回文子序列
 */
public class day02 {

    /*
     * 二叉树的层序遍历：队列
     * 将遍历的数字分为各自的层次，需要用到size来记录每层的个数一口气处理完。
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return res;
        }
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>(); // 存每一层的节点
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.pop();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                list.add(node.val);
            }
            res.add(list);
        }
        return res;
    }

    /*
     * 二叉树的锯齿层序遍历
     * 类似二叉树的层序遍历，在此基础上通过一个变量来决定用队列的头插法或尾插法
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return res;
        }
        boolean zflag = true;
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            LinkedList<Integer> list = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.pop();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                if (zflag) {
                    list.addLast(node.val);
                } else {
                    list.addFirst(node.val);
                }
            }
            res.add(list);
            zflag = !zflag;
        }
        return res;
    }

    /*
     * 二叉树的最近公共祖先
     * 对二叉树进行先序遍历，当遇到节点p或q时返回，从底至顶回溯，当节点p，q在root的异侧时，节点root即为最近公共祖先，则向上返回
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == q || root == p) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null && right == null) {
            return null; // 越过叶子节点，null
        }
        if (left == null || right == null) {
            return left == null ? right : left;
        }
        return root;
    }

    /**
     * 有效的括号：栈的应用 + map 减少 if-else 判断
     * 如果遇到了左括号，则压入栈，如果遇到了右括号，则弹栈
     * 
     * 1.如果弹出的左括号和当前右括号不匹配，则返回false
     * 2.左括号的数量多于右括号，则遍历完后stack中不为空，返回false
     * 3.右括号数量多于左括号，则在遍历期间stack为空，返回false
     */
    public boolean isValid(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }
        Deque<Object> stack = new ArrayDeque<>();
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                // 右括号多，或者弹出的左括号和当前右括号不匹配
                if (stack.isEmpty() || stack.peek() != map.get(c)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }

    /*
     * 合并有序数组：双指针 + 倒序合并
     * 当nums2指针小于0，直接返回，当nums1指针小于0，循环将nums2剩下的元素放进nums1数组
     * 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
     * 输出：[1,2,2,3,5,6]
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int idx = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] <= nums2[j]) {
                nums1[idx] = nums2[j];
                j--;
            } else {
                nums1[idx] = nums1[i];
                i--;
            }
            idx--;
        }
        // nums1指针小于0, 剩余nums2元素填充到nums1
        while (j >= 0) {
            nums1[idx] = nums2[j];
            j--;
            idx--;
        }
    }

    /*
     * 最长回文子串
     * 回文天然具有状态转移的性质，一个长度大于2的回文子串去掉首尾之后，剩下的部分依然是回文。
     * 反之，如果一个字符串头尾两个字符不相等，那它一定不是回文，动态规划的方法由此性质得到。
     */
    public String longestPalindrome(String s) {
        int start = 0, end = 0;
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i <= j; i++) {
                if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    // 如果字符串从 i 到 j 都是回文子串，只需保存最长的即可
                    if (j - i > end - start) {
                        end = j;
                        start = i;
                    }
                }
            }
        }
        return s.substring(start, end + 1);
    }

    /* 
     * 最长回文子序列
     * dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]
     * 遍历i的时候一定要从下到上遍历，这样才能保证，下一行的数据是经过计算的。
     */
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1; // 单个字符的最长回文子序列是其本身
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); // 分别加入s[i]、s[j]
                }
            }
        }
        return dp[0][n - 1];
    }

}
